﻿namespace Leetcode.N0354.V2;

public class Solution
{
    public int MaxEnvelopes(int[][] envelopes)
    {
        envelopes = envelopes.OrderBy(_ => (long)_[0] * 100000 + _[1]).ToArray();
        var result = new List<int[]>();
        result.Add(envelopes[0]);
        var stack = new Stack<int[]>();
        for (int i = 1; i < envelopes.Length; i++)
        {
            var w1 = result[result.Count - 1][0];
            var h1 = result[result.Count - 1][1];
            var w2 = envelopes[i][0];
            var h2 = envelopes[i][1];

            if (stack.Count > 0 && w2 > stack.Peek()[0])
            {
                while (stack.Count > 0)
                {
                    var item = stack.Pop();
                    var index = this.Find(result, item[1]);
                    result[index] = item;
                }

                w1 = result[result.Count - 1][0];
                h1 = result[result.Count - 1][1];
            }

            if (w2 == w1)
            {
                continue;
            }

            if (h2 > h1)
            {
                result.Add(envelopes[i]);
            }
            else if (h2 < h1)
            {
                stack.Push(envelopes[i]);
            }
        }

        return result.Count;
    }

    private int Find(IList<int[]> list, int value)
    {
        var from = 0;
        var to = list.Count - 1;
        while (from <= to)
        {
            var i = from + (to - from) / 2;
            if (value == list[i][1])
            {
                return i;
            }

            if (list[i][1] <= value)
            {
                from = i + 1;
            }
            else
            {
                to = i - 1;
            }
        }
        return from;

    }
}
